It has become common to use a flash Electrically-Erasable Programmable Read-Only Memory (flash "EEPROM") as long-term memory in computers, printers and other devices. These memories reduce the need for separate magnetic disk drives, which can be bulky, expensive, and subject to breakdown.
A flash EEPROM includes a large plurality of floating-gate field effect transistors arranged as memory cells in typical row and column format and includes circuitry for accessing the cells and placing the transistors in one of two memory conditions. These memory devices retain information even when power is removed and can be erased electrically while in place within the system with which they are used, and therefore, can be used as a long-term memory.
One disadvantage of a flash EEPROM in comparison to a hard disk is that the flash EEPROM must be erased before it can be reprogrammed, while the electromechanical hard disk can re-write the same area of a disk when information changes by changing the magnetic field stored in the area. Thus, when a file which is stored in a flash EEPROM changes, the changed information is written to a new block on an available circuit rather than written over the old data, and the old data is marked unavailable, invalid, or deleted, such as by changing a bit in the file header.
Because a flash EEPROM cannot be reprogrammed until it has been erased, valid information that remains on the device must be rewritten to some other memory area each time the EEPROM is to be erased in order for the valid information to be preserved. Otherwise, this valid information will be erased along with the invalid or unavailable information in the flash memory.
Until recently, flash EEPROMs had to be erased all at one time (i.e., portions of the EEPROM could not be erased separately from other portions of the EEPROM). With these types of flash EEPROMs, the EEPROM is erased by applying a high voltage simultaneously to the source terminals to all of the transistors (cells) used in the memory. The erasing (also known as formatting) process involves putting all memory cells in a state of logical ones.
Thus, with these types of flash EEPROM's, a spare memory equal to the size of the flash EEPROM had to be available in order to erase the EEPROM while retaining the valid data which was contained thereon. For example, if a four megabyte flash memory was used, another four megabytes of memory had to be reserved in order to erase the four megabyte flash EEPROM. This external memory could be a RAM chip, such as a static RAM or DRAM, or could comprise another flash memory array, for example. The valid files are then returned to the flash EEPROM from the external memory after the flash has been formatted. Thus, the space which is taken up by the deleted files is again made available.
U.S. Pat. No. 5,581,723, issued to Hasbun, discloses a process which allows portions of the flash EEPROM to be erased separately from other portions of the flash EEPROM. This patent discloses a method for "clean-up" of the EEPROM so that dirty sectors on it can be released. According to the process, a particular block of the flash memory to be cleaned up is selected. The selection is made based on which block of the flash array is the dirtiest and which block has been through the lowest number of clean up operation. Once the appropriate block to clean up has been chosen, available free sector space on other blocks of the flash memory is located. Once the space to store a valid sector has been located, valid data from the block being cleaned up is moved to the available space. The copying of the valid sectors on the block being cleaned up continues until all of the valid sectors on the block have been moved to the available free space. Then, the block to be cleaned up is erased separately from the other blocks on the array.
U.S. Pat. No. 5,634,050, issued to Krueger, discloses a reclamation routine which reclaims the allocated regions in a block of a flash EEPROM. According to the patent, a block may be reclaimed at several different times, such as when there is insufficient free space to satisfy an allocation request or when the ratio of de-allocated space to block size exceeds a threshold value. The flash EEPROM manager reclaims a block by copying the allocated regions to a spare block, a block that has been erased. The patent also discloses that the flash EEPROM manager could copy the allocated regions to non-flash EEPROM memory, then erase the block. According to the patent, the allocated regions can be copied to be contiguous.
While these patents disclose methods for reclaiming particular portions of a flash EEPROM device when free space is needed, they do not disclose the reclamation and defragmentation of all of the free space on the device. Thus, because all free space on the device is not made contiguous by these methods, a large contiguous file could not be written to the flash memory disclosed in these references, even after the method is performed. Thus, there is a need for a method and apparatus which allows for reclaiming space on a flash memory device on a portion-by-portion basis, and which also allows for all of the invalid space on the entire flash memory array to be reclaimed and defragmented in one continuous operation, so that all possible free space is made contiguous.
Moreover, the references do not disclose reclamation methods which allow both blocked files and contiguous files to be stored on the same flash device and which maintain the structure of the file during the reclamation process. It is desirable to save both contiguous files (a file which has all of its data stored contiguously) and blocked files (a file which has data stored in blocks which can be fragmented across the flash) on the same flash. Then, upon restoration of the space on the flash device, valid contiguous files should be returned to the flash device as contiguous files and blocked files should be returned to the flash as blocked files.
Thus, there is a need for a method and apparatus for restoring and defragmenting an entire flash memory so that all free space is made contiguous, and which can restore valid files in their original format, such that the benefits of both types of file formats (contiguous or blocked) can be retained.